package com.kevin.Code.Backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname NQueens
 * @Description Leetcode N皇后 回溯算法 困难 官方题解太精彩
 * @Date 2021/9/23 11:31
 * @Version 1.0
 */
public class NQueens {

    List<List<String>> res = new ArrayList<>();

    /**
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {

        //记录每一个皇后放在那一列
        int[] queens = new int[n];
        //赋初值-1表示 不能正确放置
        Arrays.fill(queens, -1);
        HashSet<Integer> columns = new HashSet<>();
        //用于存储左对角线
        HashSet<Integer> leftDiagonal = new HashSet<>();
        //用于存储右对角线
        HashSet<Integer> rightDiagonal = new HashSet<>();


        backtrack(columns, leftDiagonal, rightDiagonal, queens, n, 0);

        return res;
    }


    /**
     * @param columns
     * @param leftDiagonal
     * @param rightDiagonal
     * @param n
     * @param row
     */
    public void backtrack(HashSet<Integer> columns, HashSet<Integer> leftDiagonal, HashSet<Integer> rightDiagonal, int[] queens, int n, int row) {

        if (n == row) {
            List<String> subBoard = generateBoard(queens, n);
            res.add(subBoard);
        } else {
            for (int i = 0; i < n; i++) {

                if (columns.contains(i)) {
                    continue;
                }

                //如果包含左斜线 跳过
                //左斜线上得数行列相减值相同
                int left = row - i;
                if (leftDiagonal.contains(left)) {
                    continue;
                }
                //右斜线行列坐标相加和相同
                int right = row + i;
                if (rightDiagonal.contains(right)) {
                    continue;
                }
                queens[row] = i;
                columns.add(i);
                leftDiagonal.add(left);
                rightDiagonal.add(right);
                //进入下一层
                backtrack(columns, leftDiagonal, rightDiagonal, queens, n, row + 1);

                queens[row] = -1;
                columns.remove(i);
                leftDiagonal.remove(left);
                rightDiagonal.remove(right);

            }

        }

    }

    /**
     * 用于产生棋盘
     *
     * @return
     */
    public List<String> generateBoard(int[] queens, int n) {

        List<String> board = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            char[] ch = new char[n];
            Arrays.fill(ch, '.');
            ch[queens[i]] = 'Q';
            //相对而言更加节省
            board.add(new String(ch));
        }

        return board;
    }


}
